export default function maxProfit(prices: number[]): number {
  const n = prices.length;
  if (n <= 1) return 0;

  const dp: number[] = [];
  dp[0] = 0;
  let minPrice = prices[0];
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(prices[i] - minPrice, dp[i - 1]);
    minPrice = Math.min(prices[i], minPrice);
  }

  return dp[n - 1];
}

console.log(maxProfit([7, 1, 5, 3, 6, 0, 4]));
